package demo10;

public class SortDemo {
    public QuickSort createQuickSort() {
        return new QuickSort();
    }
    public MergeSort createMergeSort(){
        return new MergeSort();
    }
    public class QuickSort {
        void quickSort(int[] arr, int left, int right) {
            int index = partition(arr, left, right); // index:3
            if (left < index - 1) { // 0<3-1
                quickSort(arr, left, index - 1); // arr , 0,2
            }
            if (index < right) { // 3<5 // arr 3,5
                quickSort(arr, index, right);
            }
        }

        // 1, 4, 5, 2, 8, 9
        int partition(int[] arr, int left, int right) {
            int pivot = arr[(left + right) / 2]; // arr[2] =>5
            while (left <= right) {// 0<5
                while (arr[left] < pivot) left++; // l:2
                while (arr[right] > pivot) right--; // r:3
                if (left <= right) { // 2<=3
                    swap(arr, left, right); // 1,4,2,5,8,9
                    left++; // l:3
                    right--; // r:2
                }
            }
            return left; // return 3
        }

        void swap(int[] arr, int left, int right) {
            int temp = 0;
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }

        ;
    }

    public class MergeSort {
        void mergeSort(int[] arr) {
            int len = arr.length;
            int[] helper = new int[len];
            mergeSort(arr, helper, 0, len - 1);
        }

        void mergeSort(int[] arr, int[] helper, int low, int high) {
            if (low < high) {
                int middle = (low + high) / 2;
                mergeSort(arr, helper, low, middle);
                mergeSort(arr, helper, middle + 1, high);
                merge(arr, helper, low, middle, high);
            }
        }

        private void merge(int[] arr, int[] helper, int low, int middle, int high) {
            for (int i = low; i <= high; i++) {
                helper[i] = arr[i];
            }
            int helpLeft = low;
            int helpRight = middle + 1;
            int current = low;
            while (helpLeft <= middle && helpRight <= high) {
                if (helper[helpLeft] < helper[helpRight]) {
                    arr[current] = helper[helpLeft];
                    helpLeft++;
                } else {
                    arr[current] = helper[helpRight];
                    helpRight++;
                }
                current++;
            }
            int remaining = middle - helpLeft;
            for (int i = 0; i < remaining; i++) {
                arr[current + i] = helper[helpLeft + i];
            }

        }

    }
}
